1. Cross-Reference to Related Application
This application relates to co-pending U.S. patent application, Ser. No. 09/624,850, filed on the same day as the present application and entitled xe2x80x9cSystem and Method for Implementing a Routing Scheme in a Computer Network Using Intention Packets When Fault Conditions Are Detectedxe2x80x9d by Whay S. Lee, which is incorporated herein by reference in its entirety, and to co-pending U.S. patent application, Ser. No. 09/625,381, filed on the same day as the present application and entitled xe2x80x9cSystem and Method for Implementing a Routing Scheme Using Intention Packets in a Computer Networkxe2x80x9d by Whay S. Lee, which is incorporated herein by reference in its entirety.
2. Field of the Invention
This invention relates generally to the field of computer systems and, more particularly to communications protocols within computer systems and/or networks, and communication routing or switching within computer systems and/or networks.
3. Description of the Related Art
Devices in a communications network may communicate with one another by sending packets to each other. These packets may correspond to an operation that one device seeks to perform with the assistance of another device. Packets may be transferred between devices using a network which may include a fabric. A network generally may comprise a number of devices that are configured to convey packets between any number of devices.
At times, however, adverse transmission conditions may occur in the network when one device is sending a packet to another device on the network. For example, the network may become overly congested with packets traveling between devices. Another adverse condition that may occur in networks is corruption of a packet (e.g. an ECC error, parity error, checksum error, etc.). A fault condition (e.g. failure in the fabric) that prevents a packet from proceeding along its proposed route is another adverse condition. One adverse condition resolution scheme in packet routing protocols involves dropping packets in response to an adverse transmission condition within one or more devices (e.g. a switch, router, endpoint, node, etc.) in the network. In the case of congestion, a device within the network may drop one or more packets randomly or selectively to instantaneously reduce the packet load. By dropping one or more packets, the device can free up sufficient resources to service the remaining packets. Corrupted packets may also be dropped. For a fault condition, all packets reaching a fault point may have to be dropped and resent using a different route.
When a packet is dropped, the device that originated the packet needs to detect that it has been dropped so that it can be resent. Detection of dropped packets may be accomplished by a time-out mechanism at a receiving device when it fails to receive an expected packet, by a time-out mechanism at a sending device where the sending device is waiting for a signal from a receiving device that a packet has been received, or by sending a negative acknowledgement (NACK) from the device that dropped the packet to the sending device.
Each of these detection methods has its problems, however. Where a time-out mechanism is used, a device needs to ensure that it does not resend a packet until it is certain that the original packet has been dropped. The device must generally wait a period of time to ensure that the packet has been dropped and this waiting period results in a performance penalty. Where a NACK to the sending device is used to signal a dropped packet, a dropped packet is unknown to the receiving device, no matter how far through the network the dropped packet traveled before being dropped. The NACK propagates back only to the sender and the network resources consumed by the dropped packet are wasted. An apparatus and method of handling adverse transmission conditions that minimizes the drawbacks of the above methods is needed.
The problems outlined above may be solved by the use of the apparatus and method described herein. Generally speaking, an apparatus and method for implementing a routing scheme using intention packets is contemplated for a hierarchy of network topologies. At times, a switching device within a network level of a network hierarchy may detect an adverse transmission condition such as a fault, corruption, or congestion. When a switching device detects an adverse transmission condition, it may drop one or more packets to alleviate the adverse condition.
For example, in the case of congestion, the switching devices may support a particular amount of routing resource (e.g. bandwidth) in and out of each of their ports. When a packet or a header portion of a packet arrives at a switching device, the switching device may determine what port the packet will need and the amount of resources required by the packet on that port. If the required resources are available for the packet ion the port, then the switching device may route the packet to a next device. If the required resources are not available for the packet on the port, then the switching device may drop at least a portion of the packet. A switching device may be configured to remember the amount of resources that it has committed to other traffic and may drop a subsequent packet when it is unable to guarantee the resources requested by the subsequent packet.
When a packet is dropped due to an adverse transmission condition, the switching device that dropped it may create a second packet to be forward to the destination device. The second packet may be an intention packet that corresponds to the dropped packet. The switching device may then route or forward the intention packet to the destination device specified by the dropped packet. The intention packet may be much smaller than the dropped packet and may include a header portion or part of a header portion of the dropped packet, as discussed below. Accordingly, it may require substantially less bandwidth than the dropped packet so that a switching device may be able to guarantee its delivery to the next device if congestion was encounter. For fault conditions, the device may send the intention packet to the destination using a different route in order to avoid the fault condition.
A device may react to receiving an intention packet based on the information in the intention packet as well as its own characteristics. The information in the intention packet may indicate whether the dropped packet was a request or a response to a request. If the dropped packet was a request, then the device that receives the intention packet, i.e. the receiving device, may send a signal to the requesting device that its request has been dropped. The receiving device may also perform an operation that corresponds to the request in anticipation of receiving the resent packet. If the dropped packet was a response to a request, then the requesting device will receive the intention packet. The requesting device may reschedule the request in response to receiving the intention packet and may convey a subsequent packet that includes the request to the receiving device. The requesting device may be configured optimize the resending of the request by rescheduling the request for a more appropriate time or by merging the request with a subsequent request.
In a hierarchical network system, the routing mechanism employing intention packets may be applied to one or more network levels of the hierarchy. A common device may be coupled to two or more levels of the hierarchy. A switching device in a first level of the network hierarchy may receive a first packet from a first device in the first level. The switching device may determine if an adverse transmission condition is present. If an adverse transmission condition is present in the first network level, the switching device may drop at least part of the first packet and generate, a second packet including information about the first packet. The second packet may be conveyed to a second device. If an adverse transmission condition is not present in the first network level, the first packet is conveyed to the second device. The second device may convey a third packet onto a second network level. If an adverse transmission condition is present in the second network, at least part of said third packet may be dropped, and a fourth packet including information about the third packet may be conveyed to a third device on the second network level. The third packet may have been conveyed on the second network level in response to the second device receiving the first or second packet. The second and fourth packets may be intention packets.